/// @tags: Dinic NetFlow DivGraph
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>

int const N = 3e3 + 5, M = 2e6 + 5;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

struct Edge {
  int v, nxt, f;
} e[N * N];

int n, m, s, t, cnt, e_cnt = 1;
int heads[N], cur[N], even[N], odd[N], dis[N], pri[M / 10];
bool vis[M];

inline void add(int u, int v, int f) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].f = f;
  e[++e_cnt].v = u, e[e_cnt].nxt = heads[v], heads[v] = e_cnt, e[e_cnt].f = 0;
}

inline bool bfs() {
  memset(dis, 0, sizeof(dis));
  memcpy(cur, heads, sizeof(cur));
  std::queue<int> q;
  q.push(s), dis[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (!dis[v = e[i].v] && e[i].f) {
        dis[v] = dis[u] + 1;
        if (v == t) return true;
        q.push(v);
      }
    }
  }
  return false;
}

int dinic(int u, int flow) {
  if (u == t) return flow;
  int rest = flow, k;
  for (int i = cur[u], v; i && rest; i = e[i].nxt) {
    if (dis[v = e[i].v] == dis[u] + 1 && e[i].f) {
      k = dinic(v, std::min(rest, e[i].f));
      if (!k) dis[v] = 0;
      e[i].f -= k;
      e[i ^ 1].f += k;
      rest -= k;
      cur[u] = i;
    }
  }
  return flow - rest;
}

inline int dinic() {
  int res = 0;
  while (bfs()) res += dinic(s, 0x3f3f3f3f);
  return res;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("prime.in", "r", stdin);
  freopen("prime.out", "w", stdout);
#endif
#endif

  for (int i = 2; i < M; ++i) {
    if (!vis[i]) pri[++cnt] = i;
    for (int j = 1; j <= cnt && pri[j] * i < M; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
  while (scanf("%d%d", &n, &m) == 2) {
    memset(heads, 0, sizeof(heads));
    e_cnt = 1, *even = *odd = 0;
    s = 0, t = n + 1;
    int one = 0;
    for (int i = 1, a; i <= n; ++i) {
      read(a);
      if (!(a & 1)) even[++*even] = a;
      else if (a != 1)
        odd[++*odd] = a;
      else
        ++one;
    }
    for (int i = 1; i <= *even; ++i)
      for (int j = 1; j <= *odd; ++j)
        if (!vis[even[i] + odd[j]]) add(i, j + *even, 1);
    for (int i = 1; i <= *even; ++i) add(s, i, 1);
    for (int i = 1; i <= *odd; ++i) add(i + *even, t, 1);
    int maxflow1 = dinic();
    for (int i = 1; i <= one; ++i) add(*even + *odd + i, t, 1);
    for (int i = 1; i <= *even; ++i)
      for (int j = 1; j <= one; ++j)
        if (!vis[even[i] + 1]) add(i, j + *even + *odd, 1);
    int maxflow2 = maxflow1 + dinic(), sum = n,
        k = maxflow2 + (one - maxflow2 + maxflow1) / 2;
    for (int i = 1; i <= n - one; ++i)
      if (!e[heads[i]].nxt) --sum;
    printf("%d\n", k > m ? m * 2 : std::min(sum, m + k));
  }
  return 0;
}